package com.samxcode.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Given n pairs of parentheses, write a function to generate all combinations of well-formed
 * parentheses.
 * 
 * DP f(k) denotes all combinations of k pairs of parentheses f(0):"" f(1):"(f(0))"
 * f(2):"(f(0))f(1)","(f(1))f(0)" ....f(n):"(f(0))f(n - 1)"...."(f(n - 1))f(0)"
 * 
 * @author Sam
 *
 */
public class GenerateParentheses {

    public static void main(String[] args) {
        System.out.println(generateParenthesis(6));
    }

    public static List<String> generateParenthesis(int n) {
        List<LinkedList<String>> res = new ArrayList<LinkedList<String>>();
        res.add(new LinkedList<String>());
        res.get(0).add("");
        for (int i = 1; i <= n; i++) {
            LinkedList<String> list = new LinkedList<String>();
            for (int j = 0; j < i; j++) {
                for (String s1 : res.get(j)) {
                    for (String s2 : res.get(i - j - 1)) {
                        list.add("(" + s1 + ")" + s2);
                    }
                }
            }
            res.add(list);
        }
        return res.get(n);
    }
}
